package tech.aistar.corejava.day11;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author success
 * @version 1.0
 * @description:本类用来演示:括号匹配
 * @date 2019/7/29 0029
 */
public class BracketDemo {
    /**
     * 栈顶:
     *`
     *
     * 思路 - [{()}] - 控制台输入的一个字符串
     * 1 - 将字符串转换字符数组 char[] toCharArray(); - arr
     * 2 - 创建一个LinkedList<Character> list
     * 3 - 将字符数组的第一个元素压入栈顶 - list.push(arr[0]);
     * 4 - 从字符数组的第二个位置开始向后遍历,永远和栈顶的元素进行比较.
     *     栈顶元素: [
     *     第二个位置:{
     *     发现[和{不匹配,继续将arr数组当前位置的元素继续压入栈顶
     *     list.push(arr[i]);
     *
     *     当i = 2的时候
     *     栈顶:{
     *     arr[2]:(
     *     继续压入栈顶 - arr[2]
     *
     *     当i = 3的时候
     *     栈顶:(
     *     arr[3]:)
     *     发现匹配,弹出栈顶内容 - list.pop();
     *
     *     i = 4
     *     栈顶:{
     *     arr[4]:}
     *
     *     匹配:继续弹出栈顶内容 - list.pop()
     *
     *     i = 5:
     *     栈顶:[
     *     arr[5] = ]
     *     弹出栈顶 - 发现LinkedList集合没有元素了 - 说明是括号是匹配的
     *
     * Bug - java.util.NoSuchElementException
     * ()[]{}
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请你输入括号:>");

        String line = sc.nextLine();

       boolean flag =  match(line);
       if(flag){
           System.out.println("匹配!");
       }else{
           System.out.println("不匹配!");
       }

    }

    /**
     *
     * @param line 括号
     * @return
     */
    public static boolean match(String line){
        //1. 将字符串转换成字符数组
        char[] arr = line.toCharArray();

        //2. 创建一个LinkedList集合
        LinkedList<Character> list = new LinkedList<>();

        //3.将字符数组中的第一个元素压入栈顶.
        list.push(arr[0]);

        //4. 从字符数组的第二个元素开始进行遍历
        for (int i = 1; i < arr.length; i++) {
            //5. 永远拿arr[i]和栈顶元素进行比较.
            //5-1. 获取栈顶的内容
            //()[]{}
            //判断栈顶是否存在元素
            Character c1 = null;
            Character c2 = arr[i];
            if(list.isEmpty()){//不存在栈顶元素
                //将当前的c2压入栈顶
                list.push(c2);
                continue;
            }
            //存在栈顶
            c1 = list.getFirst();

            if(c1.equals('(') && c2.equals(')') || c1.equals('[') && c2.equals(']') || c1.equals('{') && c2.equals('}')){
                //弹出栈顶内容
                list.pop();
            }else{
                //将当前的arr[i]压入栈顶
                list.push(c2);
            }
        }
        return list.isEmpty();//如果集合为空,说明是匹配
    }
}
